#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a,b;
int dp[10][5005];
int d[10];
int len;
int f(int n){
    int ans=0;
    int k=1;
    while(n){
        ans+=n%10*k;
        k*=2;
        n/=10;
    }
    return ans;
}
void init(){
    //dp[i][j]表示前i位数字中函数值等于j的个数
    dp[0][0]=1;
    for(int i=1;i<=9;i++){
        for(int j=0;j<5000;j++){
            //k是枚举每一位十进制数，相当于打表了
            for(int k=0;k<=9;k++){
                if(j-k*(1<<(i-1))>=0){
                    //状态转移，从i-1位转移
                    dp[i][j]+=dp[i-1][j-k*(1<<(i-1))];
                }
            }
        }
    }
    //j从小依次累计，现在
    //dp[i][j]表示前i位数字中函数值小于j的个数
    for(int i=1;i<=9;i++){
        for(int j=1;j<5000;j++){
            dp[i][j]+=dp[i][j-1];
        }
    }
}
int solve(int k,int num){
    //printf("%d %d\n",k,num);
    k++;
    if(num<0 || k<0){
        return 0;
    }
    if(k==1){
        return min(num,d[0])+1; 
    }
    if(num==0){
        return 1;
    }
    int t=d[k-1];
    //printf("%d\n",t);
    int ans=0;
    for(int i=0;i<t;i++){
        if(num-i*(1<<(k-1))>=0){
            ans+=dp[k-1][num-i*(1<<(k-1))];
        }
    }
    ans+=solve(k-2,num-t*(1<<(k-1)));
    return ans;
}
int main(void){
    int t;
    init();
    scanf("%d",&t);
    for(int c=1;c<=t;c++){
        scanf("%d%d",&a,&b);
        memset(d,0,sizeof(d));
        len=0;
        //记录b数的数位
        while(b){
            d[len++]=b%10;
            b/=10;
        }
        int ans=solve(len,f(a));
        printf("Case #%d: %d\n",c,ans);
    }
    return 0;
}